package binarytree

func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := 1
	left := root
	for left.Left != nil {
		leftDepth++
		left = left.Left
	}

	rightDepth := 1
	right := root
	for right.Right != nil {
		rightDepth++
		right = right.Right
	}

	if leftDepth == rightDepth {
		return (1 << leftDepth) - 1
	}
	return 1 + countNodes(root.Left) + countNodes(root.Right)
}
